home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / CUGUK / COMMS / C011.ZIP / SQ.C < prev    next >
Text File  |  1990-01-19  |  22KB  |  790 lines
  1. /********************************************************************
  2.  * C Users Group (U.K) C Source Code Library File CUGLIB.011        *
  3.  * Inquiries to: M. Houston, 36 Whetstone Clo. Farquhar Rd.         *
  4.  * Edgbaston, Birmingham B15 2QN ENGLAND                *
  5.  ********************************************************************
  6.  * File name: sq.c
  7.  * Program name: sq
  8.  * Source of file: The Public Domain Software Library.
  9.  * Purpose: file squeeze program
  10.  * Changes: <who what when & why major changes have been made>      
  11.  ********************************************************************/
  12.  
  13. /*% cc -O -n % -o sq
  14. */
  15. #include <stdio.h>
  16. #define TRUE 1
  17. #define rewind(c) fseek(c,0L,0);                       /* 1.7 */
  18. #define FALSE 0
  19. #define ERROR (-1)
  20. #define PATHLEN 312    /* Number of characters allowed in pathname */
  21. #define ALTNAME "sq.out"
  22.  
  23. /* Definitions and external declarations */
  24. #define RECOGNIZE 0xFF76    /* unlikely pattern */
  25. /* *** Stuff for first translation module *** */
  26. #define DLE 0x90
  27.  
  28.  
  29. /* *** Stuff for second translation module *** */
  30. #define SPEOF 256    /* special endfile token */
  31. #define NUMVALS 257    /* 256 data values plus SPEOF*/
  32. /* Definitions and external declarations */
  33. int Usestd;    /* Use stdout for squeezed output */
  34. unsigned crc;    /* error check code */
  35. /* *** Stuff for first translation module *** */
  36. int likect;    /*count of consecutive identical chars */
  37. int lastchar, newchar;
  38. char state;
  39. /* states */
  40. #define NOHIST    0    /*don't consider previous input*/
  41. #define SENTCHAR 1    /*lastchar set, no lookahead yet */
  42. #define SENDNEWC 2    /*newchar set, previous sequence done */
  43. #define SENDCNT 3    /*newchar set, DLE sent, send count next */
  44.  
  45. /* *** Stuff for second translation module *** */
  46. #define NOCHILD -1    /* indicates end of path through tree */
  47. #define NUMNODES (NUMVALS + NUMVALS - 1)    /* nbr of nodes */
  48.  
  49. #define MAXCOUNT 65535    /* biggest unsigned integer */
  50.  
  51. /* The following array of structures are the nodes of the
  52.  * binary trees. The first NUMVALS nodes becomethe leaves of the
  53.  * final tree and represent the values of the data bytes being
  54.  * encoded and the special endfile, SPEOF.
  55.  * The remaining nodes become the internal nodes of the final tree.
  56.  */
  57.  
  58. struct    nd {
  59.     unsigned weight;    /* number of appearances */
  60.     int tdepth;        /* length on longest path in tre*/
  61.     int lchild, rchild;    /* indexes to next level */
  62. }
  63. node[NUMNODES];
  64.  
  65. int dctreehd;    /*index to head node of final tree */
  66.  
  67. /* This is the encoding table:
  68.  * The bit strings have first bit in  low bit.
  69.  * Note that counts were scaled so code fits unsigned integer
  70.  */
  71.  
  72. int codelen[NUMVALS];        /* number of bits in code */
  73. unsigned code[NUMVALS];     /* code itself, right adjusted */
  74. unsigned tcode;         /* temporary code value */
  75.  
  76.  
  77. /* Variables used by encoding process */
  78. int curin;    /* Value currently being encoded */
  79. int cbitsrem;    /* Number of code string bits remaining */
  80. unsigned ccode; /* Current code shifted so next code bit is at right */
  81. /* This program compresses a file without losing information.
  82.  * The usq.com program is required to unsqueeze the file
  83.  * before it can be used.
  84.  *
  85.  * Typical compression rates are:
  86.  *    .COM    6%    (Don't bother)
  87.  *    .ASM    33%    (using full ASCII set)
  88.  *    .DIC    46%    (using only uppercase and a few others)
  89.  * Squeezing a really big file takes a few minutes.
  90.  *
  91.  * Useage:
  92.  *    sq file ...
  93.  *
  94.  *
  95.  * The squeezed file name is formed by changing the second from last
  96.  * letter of the file type to Q. If there is no file type,
  97.  * the squeezed file type is QQQ. If the name exists it is
  98.  * overwritten!
  99.  *
  100.  * The transformations compress strings of identical bytes and
  101.  * then encode each resulting byte value and EOF as bit strings
  102.  * having lengths in inverse proportion to their frequency of
  103.  * occurrance in the intermediate input stream. The latter uses
  104.  * the Huffman algorithm. Decoding information is included in
  105.  * the squeezed file, so squeezing short files or files with
  106.  * uniformly distributed byte values will actually increase size.
  107.  */
  108.  
  109. /* CHANGE HISTORY:
  110.  * 1.5u **nix version - means output to stdout.
  111.  *  (stdin not allowed becuase sq needs to rewind input, which
  112.  *  won't work with pipes.)
  113.  * Filename generation changed to suit **nix and stdio.
  114.  * 1.6u machine independent output for file compatibility with
  115.  *    original CP/M version SQ, when running on machine with
  116.  *    IBM byte ordering such as Z8000 and 68000.
  117.  *
  118.  * 1.7    08/13/83  C86 Version by Wayne Fruhwald
  119.  *    Converted to work with Computer Innovation's C86 c compiler under MSDOS.
  120.  *
  121.  */
  122.  
  123. #define VERSION "1.7    8-13-83"                                       /* 1.7 */
  124.  
  125. main(argc, argv)
  126. int argc;
  127. char *argv[];
  128. {
  129.     register i,c;
  130.  
  131.  
  132.     /* Process the parameters in order */
  133.     for(i = 1; i < argc; ++i) {
  134.         if(strcmp(argv[i], "-")==0)
  135.             Usestd = TRUE;
  136.     }
  137.     for(i = 1; i < argc; ++i) {
  138.         if(strcmp(argv[i], "-")!=0)
  139.             obey(argv[i]);
  140.     }
  141.  
  142.     if(argc < 2) {
  143.         fprintf(stderr,"File squeezer version %s by\n\tRichard Greenlaw\n\t251 Colony Ct.\n\tGahanna, Ohio 43230\n", VERSION);
  144.         fprintf(stderr, "Usage: sq [-] pathname ...\n");
  145.         fprintf(stderr, "\t- squeezed output to stdout\n");
  146.         exit(1);
  147.     }
  148.     exit(0);
  149. }
  150.  
  151. obey(p)
  152. char *p;
  153. {
  154.     char *w,*q;
  155.     char outfile[PATHLEN+2];    /* output file spec. */
  156.  
  157.     /* First build output file name */
  158.  
  159.     strcpy(outfile, p);
  160.     /* Find and change output file type */
  161.     for(w=q = outfile; *q != '\0'; ++q)     /* skip leading /'s */
  162.         if( *q == '/')
  163.             w = q+1;
  164.     for(q = w; *q != '\0'; ++q)
  165.         if(*q == '.')
  166.             if(*(q + 1) == '\0')
  167.                 *q = '\0';      /* kill trailing dot */
  168.             else
  169.                 switch(*(q+2)) {
  170.                 case 'q':
  171.                 case 'Q':
  172.                     fprintf(stderr, "\n%s ignored ( already squeezed?)", p);
  173.                     return;
  174.                 case '\0':
  175.                     *(q+3) = '\0';
  176.                     /* fall thru */
  177.                 default:
  178.                     *(q + 2) = 'Q';
  179.                     goto named;
  180.                 }
  181.     /* No file type */
  182.     strcat(outfile, ".QQQ");
  183. named:
  184.     if(strlen(w)>14)
  185.         strcpy(outfile, ALTNAME);    /* check for too long name */
  186.     squeeze(p, outfile);
  187. }
  188.  
  189. squeeze(infile, outfile)
  190. char *infile, *outfile;
  191. {
  192.     register i, c;
  193.     FILE *inbuff, *outbuff; /* file buffers */
  194.  
  195.     fprintf(stderr, "\n%s -> %s: ", infile, outfile);
  196.  
  197.     if((inbuff=fopen(infile, "rb")) == NULL) {                     /* 1.7 */
  198.         fprintf(stderr, "Can't open %s for input pass 1\n", infile);
  199.         return;
  200.     }
  201.     if(Usestd)
  202.         outbuff=stdout;
  203.     else if((outbuff=fopen(outfile, "wb")) == NULL) {              /* 1.7 */
  204.         fprintf(stderr, "Can't create %s\n", outfile);
  205.         fclose(inbuff);
  206.         return;
  207.     }
  208.  
  209.     /* First pass - get properties of file */
  210.     crc = 0;    /* initialize checksum */
  211.     fprintf(stderr, "analyzing, ");
  212.     init_ncr();
  213.     init_huff(inbuff);
  214.     rewind(inbuff);
  215.     /* Write output file header with decoding info */
  216.     wrt_head(outbuff, infile);
  217.  
  218.     /* Second pass - encode the file */
  219.     fprintf(stderr, "squeezing, ");
  220.  
  221.     init_ncr();    /* For second pass */
  222.  
  223.     /* Translate the input file into the output file */
  224.     while((c = gethuff(inbuff)) != EOF)
  225.         if(putc(c, outbuff) == ERROR && ferror(outbuff)) {
  226.             fprintf(stderr, "ERROR - write failure in %s\n", outfile);
  227.             goto closeall;
  228.         }
  229.     fprintf(stderr, " done.\n");
  230. closeall:
  231.     fclose(inbuff);
  232. closeout:
  233.     fflush(outbuff);
  234.     fclose(outbuff);
  235. }
  236.  
  237.  
  238. /* First translation - encoding of repeated characters
  239.  * The code is byte for byte pass through except that
  240.  * DLE is encoded as DLE, zero and repeated byte values
  241.  * are encoded as value, DLE, count for count >= 3.
  242.  */
  243.  
  244. init_ncr()    /*initialize getcnr() */
  245. {
  246.     state = NOHIST;
  247. }
  248.  
  249. int
  250. getcnr(iob)
  251. FILE *iob;
  252. {
  253.     switch(state) {
  254.     case NOHIST:
  255.         /* No relevant history */
  256.         state = SENTCHAR;
  257.         return lastchar = getc_crc(iob);
  258.     case SENTCHAR:
  259.         /* Lastchar is set, need lookahead */
  260.         switch(lastchar) {
  261.         case DLE:
  262.             state = NOHIST;
  263.             return 0;    /* indicates DLE was the data */
  264.         case EOF:
  265.             return EOF;
  266.         default:
  267.             for(likect = 1; (newchar = getc_crc(iob)) == lastchar && likect < 255; ++likect)
  268.                 ;
  269.             switch(likect) {
  270.             case 1:
  271.                 return lastchar = newchar;
  272.             case 2:
  273.                 /* just pass through */
  274.                 state = SENDNEWC;
  275.                 return lastchar;
  276.             default:
  277.                 state = SENDCNT;
  278.                 return DLE;
  279.             }
  280.         }
  281.     case SENDNEWC:
  282.         /* Previous sequence complete, newchar set */
  283.         state = SENTCHAR;
  284.         return lastchar = newchar;
  285.     case SENDCNT:
  286.         /* Sent DLE for repeat sequence, send count */
  287.         state = SENDNEWC;
  288.         return likect;
  289.     default:
  290.         fprintf(stderr,"Bug - bad state\n");
  291.         exit(1);
  292.         /* NOTREACHED */
  293.     }
  294. }
  295.  
  296.  
  297. /******** Second translation - bytes to variable length bit strings *********/
  298.  
  299.  
  300. /* This translation uses the Huffman algorithm to develop a
  301.  * binary tree representing the decoding information for
  302.  * a variable length bit string code for each input value.
  303.  * Each string's length is in inverse proportion to its
  304.  * frequency of appearance in the incoming data stream.
  305.  * The encoding table is derived from the decoding table.
  306.  *
  307.  * The range of valid values into the Huffman algorithm are
  308.  * the values of a byte stored in an integer plus the special
  309.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  310.  *
  311.  * The "node" array of structures contains the nodes of the
  312.  * binary tree. The first NUMVALS nodes are the leaves of the
  313.  * tree and represent the values of the data bytes being
  314.  * encoded and the special endfile, SPEOF.
  315.  * The remaining nodes become the internal nodes of the tree.
  316.  *
  317.  * In the original design it was believed that
  318.  * a Huffman code would fit in the same number of
  319.  * bits that will hold the sum of all the counts.
  320.  * That was disproven by a user's file and was a rare but
  321.  * infamous bug. This version attempts to choose among equally
  322.  * weighted subtrees according to their maximum depths to avoid
  323.  * unnecessarily long codes. In case that is not sufficient
  324.  * to guarantee codes <= 16 bits long, we initially scale
  325.  * the counts so the total fits in an unsigned integer, but
  326.  * if codes longer than 16 bits are generated the counts are
  327.  * rescaled to a lower ceiling and code generation is retried.
  328.  */
  329.  
  330. /* Initialize the Huffman translation. This requires reading
  331.  * the input file through any preceding translation functions
  332.  * to get the frequency distribution of the various values.
  333.  */
  334.  
  335. init_huff(ib)
  336. FILE *ib;
  337. {
  338.     register c, i;
  339.     int btlist[NUMVALS];    /* list of intermediate binary trees */
  340.     int listlen;        /* length of btlist */
  341.     unsigned *wp;        /* simplifies weight counting */
  342.     unsigned ceiling;    /* limit for scaling */
  343.  
  344.     /* Initialize tree nodes to no weight, no children */
  345.     init_tree();
  346.  
  347.     /* Build frequency info in tree */
  348.     do {
  349.         c = getcnr(ib);
  350.         if(c == EOF)
  351.             c = SPEOF;
  352.         if(*(wp = &node[c].weight) !=  MAXCOUNT)
  353.             ++(*wp);
  354.     }
  355.     while(c != SPEOF);
  356.  
  357.     ceiling = MAXCOUNT;
  358.  
  359.     do {    /* Keep trying to scale and encode */
  360.         if(ceiling != MAXCOUNT)
  361.             fprintf(stderr, "*** rescaling ***, ");
  362.         scale(ceiling);
  363.         ceiling /= 2;    /* in case we rescale */
  364.  
  365.         /* Build list of single node binary trees having
  366.                  * leaves for the input values with non-zero counts
  367.                  */
  368.         for(i = listlen = 0; i < NUMVALS; ++i)
  369.             if(node[i].weight != 0) {
  370.                 node[i].tdepth = 0;
  371.                 btlist[listlen++] = i;
  372.             }
  373.  
  374.         /* Arrange list of trees into a heap with the entry
  375.                  * indexing the node with the least weight at the top.
  376.                  */
  377.         heap(btlist, listlen);
  378.  
  379.         /* Convert the list of trees to a single decoding tree */
  380.         bld_tree(btlist, listlen);
  381.  
  382.         /* Initialize the encoding table */
  383.         init_enc();
  384.  
  385.         /* Try to build encoding table.
  386.                  * Fail if any code is > 16 bits long.
  387.                  */
  388.     }
  389.     while(buildenc(0, dctreehd) == ERROR);
  390.  
  391.     /* Initialize encoding variables */
  392.     cbitsrem = 0;    /*force initial read */
  393.     curin = 0;    /*anything but endfile*/
  394. }
  395.  
  396. /* The count of number of occurrances of each input value
  397.  * have already been prevented from exceeding MAXCOUNT.
  398.  * Now we must scale them so that their sum doesn't exceed
  399.  * ceiling and yet no non-zero count can become zero.
  400.  * This scaling prevents errors in the weights of the
  401.  * interior nodes of the Huffman tree and also ensures that
  402.  * the codes will fit in an unsigned integer. Rescaling is
  403.  * used if necessary to limit the code length.
  404.  */
  405.  
  406. scale(ceil)
  407. unsigned ceil;    /* upper limit on total weight */
  408. {
  409.     register i,c;
  410.     int ovflw, divisor;
  411.     unsigned w, sum;
  412.     char increased;     /* flag */
  413.  
  414.     do {
  415.         for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  416.             if(node[i].weight > (ceil - sum))
  417.                 ++ovflw;
  418.             sum += node[i].weight;
  419.         }
  420.  
  421.         divisor = ovflw + 1;
  422.  
  423.         /* Ensure no non-zero values are lost */
  424.         increased = FALSE;
  425.         for(i = 0; i < NUMVALS; ++i) {
  426.             w = node[i].weight;
  427.             if (w < divisor && w != 0) {
  428.                 /* Don't fail to provide a code if it's used at all */
  429.                 node[i].weight = divisor;
  430.                 increased = TRUE;
  431.             }
  432.         }
  433.     }
  434.     while(increased);
  435.  
  436.     /* Scaling factor choosen, now scale */
  437.     if(divisor > 1)
  438.         for(i = 0; i < NUMVALS; ++i)
  439.             node[i].weight /= divisor;
  440. }
  441.  
  442. /* heap() and adjust() maintain a list of binary trees as a
  443.  * heap with the top indexing the binary tree on the list
  444.  * which has the least weight or, in case of equal weights,
  445.  * least depth in its longest path. The depth part is not
  446.  * strictly necessary, but tends to avoid long codes which
  447.  * might provoke rescaling.
  448.  */
  449.  
  450. heap(list, length)
  451. int list[], length;
  452. {
  453.     register i;
  454.  
  455.     for(i = (length - 2) / 2; i >= 0; --i)
  456.         adjust(list, i, length - 1);
  457. }
  458.  
  459. /* Make a heap from a heap with a new top */
  460.  
  461. adjust(list, top, bottom)
  462. int list[], top, bottom;
  463. {
  464.     register k, temp;
  465.  
  466.     k = 2 * top + 1;    /* left child of top */
  467.     temp = list[top];    /* remember root node of top tree */
  468.     if( k <= bottom) {
  469.         if( k < bottom && cmptrees(list[k], list[k + 1]))
  470.             ++k;
  471.  
  472.         /* k indexes "smaller" child (in heap of trees) of top */
  473.         /* now make top index "smaller" of old top and smallest child */
  474.         if(cmptrees(temp, list[k])) {
  475.             list[top] = list[k];
  476.             list[k] = temp;
  477.             /* Make the changed list a heap */
  478.             adjust(list, k, bottom); /*recursive*/
  479.         }
  480.     }
  481. }
  482.  
  483. /* Compare two trees, if a > b return true, else return false
  484.  * note comparison rules in previous comments.
  485.  */
  486.  
  487. cmptrees(a, b)
  488. register int a, b;  /* root nodes of trees */
  489. {
  490.     if(node[a].weight > node[b].weight)
  491.         return TRUE;
  492.     if(node[a].weight == node[b].weight)
  493.         if(node[a].tdepth > node[b].tdepth)
  494.             return TRUE;
  495.     return FALSE;
  496. }
  497.  
  498. /* HUFFMAN ALGORITHM: develops the single element trees
  499.  * into a single binary tree by forming subtrees rooted in
  500.  * interior nodes having weights equal to the sum of weights of all
  501.  * their descendents and having depth counts indicating the
  502.  * depth of their longest paths.
  503.  *
  504.  * When all trees have been formed into a single tree satisfying
  505.  * the heap property (on weight, with depth as a tie breaker)
  506.  * then the binary code assigned to a leaf (value to be encoded)
  507.  * is then the series of left (0) and right (1)
  508.  * paths leading from the root to the leaf.
  509.  * Note that trees are removed from the heaped list by
  510.  * moving the last element over the top element and
  511.  * reheaping the shorter list.
  512.  */
  513.  
  514. bld_tree(list, len)
  515. int list[];
  516. int len;
  517. {
  518.     register freenode;        /* next free node in tree */
  519.     register struct nd *frnp;    /* free node pointer */
  520.     int lch, rch;        /* temporaries for left, right children */
  521.     int i;
  522.  
  523.     /* Initialize index to next available (non-leaf) node.
  524.          * Lower numbered nodes correspond to leaves (data values).
  525.          */
  526.     freenode = NUMVALS;
  527.  
  528.     while(len > 1) {
  529.         /* Take from list two btrees with least weight
  530.                  * and build an interior node pointing to them.
  531.                  * This forms a new tree.
  532.                  */
  533.         lch = list[0];    /* This one will be left child */
  534.  
  535.         /* delete top (least) tree from the list of trees */
  536.         list[0] = list[--len];
  537.         adjust(list, 0, len - 1);
  538.  
  539.         /* Take new top (least) tree. Reuse list slot later */
  540.         rch = list[0];    /* This one will be right child */
  541.  
  542.         /* Form new tree from the two least trees using
  543.                  * a free node as root. Put the new tree in the list.
  544.                  */
  545.         frnp = &node[freenode]; /* address of next free node */
  546.         list[0] = freenode++;    /* put at top for now */
  547.         frnp->lchild = lch;
  548.         frnp->rchild = rch;
  549.         frnp->weight = node[lch].weight + node[rch].weight;
  550.         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  551.         /* reheap list    to get least tree at top*/
  552.         adjust(list, 0, len - 1);
  553.     }
  554.     dctreehd = list[0];    /*head of final tree */
  555. }
  556.  
  557. /* ???????????? */
  558. maxchar(a, b)
  559. {
  560.     return a > b ? a : b;
  561. }
  562. /* Initialize all nodes to single element binary trees
  563.  * with zero weight and depth.
  564.  */
  565.  
  566. init_tree()
  567. {
  568.     register i;
  569.  
  570.     for(i = 0; i < NUMNODES; ++i) {
  571.         node[i].weight = 0;
  572.         node[i].tdepth = 0;
  573.         node[i].lchild = NOCHILD;
  574.         node[i].rchild = NOCHILD;
  575.     }
  576. }
  577.  
  578. init_enc()
  579. {
  580.     register i;
  581.  
  582.     /* Initialize encoding table */
  583.     for(i = 0; i < NUMVALS; ++i) {
  584.         codelen[i] = 0;
  585.     }
  586. }
  587.  
  588. /* Recursive routine to walk the indicated subtree and level
  589.  * and maintain the current path code in bstree. When a leaf
  590.  * is found the entire code string and length are put into
  591.  * the encoding table entry for the leaf's data value.
  592.  *
  593.  * Returns ERROR if codes are too long.
  594.  */
  595.  
  596. int        /* returns ERROR or NULL */
  597. buildenc(level, root)
  598. int level;/* level of tree being examined, from zero */
  599. int root; /* root of subtree is also data value if leaf */
  600. {
  601.     register l, r;
  602.  
  603.     l = node[root].lchild;
  604.     r = node[root].rchild;
  605.  
  606.     if( l == NOCHILD && r == NOCHILD) {
  607.         /* Leaf. Previous path determines bit string
  608.                  * code of length level (bits 0 to level - 1).
  609.                  * Ensures unused code bits are zero.
  610.                  */
  611.         codelen[root] = level;
  612.         code[root] = tcode & (((unsigned)~0) >> (16 - level));
  613.         return (level > 16) ? ERROR : NULL;
  614.     }
  615.     else {
  616.         if( l != NOCHILD) {
  617.             /* Clear path bit and continue deeper */
  618.             tcode &= ~(1 << level);
  619.             /* NOTE RECURSION */
  620.             if(buildenc(level + 1, l) == ERROR)
  621.                 return ERROR;
  622.         }
  623.         if(r != NOCHILD) {
  624.             /* Set path bit and continue deeper */
  625.             tcode |= 1 << level;
  626.             /* NOTE RECURSION */
  627.             if(buildenc(level + 1, r) == ERROR)
  628.                 return ERROR;
  629.         }
  630.     }
  631.     return NULL;    /* if we got here we're ok so far */
  632. }
  633.  
  634. /* Write out the header of the compressed file */
  635.  
  636. wrt_head(ob, infile)
  637. FILE *ob;
  638. char *infile;    /* input file name (w/ or w/o drive) */
  639. {
  640.     register l,r;
  641.     int i, k;
  642.     int numnodes;        /* nbr of nodes in simplified tree */
  643.  
  644.     putwe(RECOGNIZE, ob);    /* identifies as compressed */
  645.     putwe(crc, ob);     /* unsigned sum of original data */
  646.  
  647.     /* Record the original file name w/o drive */
  648.     if(*(infile + 1) == ':')
  649.         infile += 2;    /* skip drive */
  650.  
  651.     do {
  652.         putce(*infile, ob);
  653.     }
  654.     while(*(infile++) != '\0');
  655.  
  656.  
  657.     /* Write out a simplified decoding tree. Only the interior
  658.          * nodes are written. When a child is a leaf index
  659.          * (representing a data value) it is recoded as
  660.          * -(index + 1) to distinguish it from interior indexes
  661.          * which are recoded as positive indexes in the new tree.
  662.          * Note that this tree will be empty for an empty file.
  663.          */
  664.  
  665.     numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
  666.     putwe(numnodes, ob);
  667.  
  668.     for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
  669.         l = node[i].lchild;
  670.         r = node[i].rchild;
  671.         l = l < NUMVALS ? -(l + 1) : dctreehd - l;
  672.         r = r < NUMVALS ? -(r + 1) : dctreehd - r;
  673.         putwe(l, ob);    /* left child */
  674.         putwe(r, ob);    /* right child */
  675.     }
  676. }
  677.  
  678. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  679.  *
  680.  * There are two unsynchronized bit-byte relationships here.
  681.  * The input stream bytes are converted to bit strings of
  682.  * various lengths via the static variables named c...
  683.  * These bit strings are concatenated without padding to
  684.  * become the stream of encoded result bytes, which this
  685.  * function returns one at a time. The EOF (end of file) is
  686.  * converted to SPEOF for convenience and encoded like any
  687.  * other input value. True EOF is returned after that.
  688.  *
  689.  * The original gethuff() called a seperate function,
  690.  * getbit(), but that more readable version was too slow.
  691.  */
  692.  
  693. int        /*  Returns byte values except for EOF */
  694. gethuff(ib)
  695. FILE *ib;
  696. {
  697.     int rbyte;    /* Result byte value */
  698.     int need, take; /* numbers of bits */
  699.  
  700.     rbyte = 0;
  701.     need = 8;    /* build one byte per call */
  702.  
  703.     /* Loop to build a byte of encoded data
  704.          * Initialization forces read the first time
  705.          */
  706.  
  707. loop:
  708.     if(cbitsrem >= need) {
  709.         /* Current code fullfills our needs */
  710.         if(need == 0)
  711.             return rbyte;
  712.         /* Take what we need */
  713.         rbyte |= ccode << (8 - need);
  714.         /* And leave the rest */
  715.         ccode >>= need;
  716.         cbitsrem -= need;
  717.         return rbyte;
  718.     }
  719.  
  720.     /* We need more than current code */
  721.     if(cbitsrem > 0) {
  722.         /* Take what there is */
  723.         rbyte |= ccode << (8 - need);
  724.         need -= cbitsrem;
  725.     }
  726.     /* No more bits in current code string */
  727.     if(curin == SPEOF) {
  728.         /* The end of file token has been encoded. If
  729.                  * result byte has data return it and do EOF next time
  730.                  */
  731.         cbitsrem = 0;
  732.  
  733.         /*NOTE: +0 is to fight compiler bug? */
  734.         return (need == 8) ? EOF : rbyte + 0;
  735.     }
  736.  
  737.     /* Get an input byte */
  738.     if((curin = getcnr(ib)) == EOF)
  739.         curin = SPEOF;    /* convenient for encoding */
  740.  
  741.     /* Get the new byte's code */
  742.     ccode = code[curin];
  743.     cbitsrem = codelen[curin];
  744.  
  745.     goto loop;
  746. }
  747.  
  748.  
  749. /* Get next byte from file and update checksum */
  750.  
  751. int
  752. getc_crc(ib)
  753. FILE *ib;
  754. {
  755.     register c;
  756.  
  757.     c = getc(ib);
  758.     if(c != EOF)
  759.         crc += c;    /* checksum */
  760.     return c;
  761. }
  762.  
  763. /* Output functions with error reporting */
  764.  
  765. putce(c, iob)
  766. int c;
  767. register FILE *iob;
  768. {
  769.     if(putc(c, iob) == ERROR && ferror(iob)) {
  770.         fprintf(stderr, "sq:Write error\n");
  771.         exit(1);
  772.     }
  773. }
  774.  
  775. /*
  776.  * machine independent put-word that writes low order byte first
  777.  *  (compatible with CP/M original) regardless of host cpu.
  778.  */
  779. putwe(w, iob)
  780. register int w;
  781. register FILE *iob;
  782. {
  783.     putc(w, iob);
  784.     putc(w>>8, iob);
  785.     if (ferror(iob)) {
  786.         fprintf(stderr, "sq:Write error\n");
  787.         exit(1);
  788.     }
  789. }
  790.